package com.jason.java.lib;

/**
 * Description:Coins
 *
 * @author jason
 * @create 2020/9/15 16:38
 */
public class Coins {

  public static void main(String[] args) {
    int coins[] = { 1, 2, 5 };
    int amount = 11;
    int result = getMinCoinNum(coins, amount);
    System.out.println("coins = " + coins + "，amount = " + amount + "，结果：" + result);

    int coins2[] = { 2 };
    int amount2 = 5;
    int result2 = getMinCoinNum(coins2, amount2);
    System.out.println("coins = " + coins2 + "，amount = " + amount2 + "，结果：" + result2);

    int coins3[] = { 2, 3, 5 };
    int amount3 = 29;
    int result3 = getMinCoinNum(coins3, amount3);
    System.out.println("coins = " + coins3 + "，amount = " + amount3 + "，结果：" + result3);

    int coins4[] = { 2, 3, 7 };
    int amount4 = 29;
    int result4 = getMinCoinNum(coins4, amount4);
    System.out.println("coins = " + coins4 + "，amount = " + amount4 + "，结果：" + result4);

    int coins5[] = { 1, 2, 3, 5 };
    int amount5 = 23;
    int result5 = getMinCoinNum(coins5, amount5);
    System.out.println("coins = " + coins5 + "，amount = " + amount5 + "，结果：" + result5);

    int coins6[] = { 3, 7, 4, 5 };
    int amount6 = 23;
    int result6 = getMinCoinNum(coins6, amount6);
    System.out.println("coins = " + coins6 + "，amount = " + amount6 + "，结果：" + result6);

    int coins7[] = { 3, 7 };
    int amount7 = 22;
    int result7 = getMinCoinNum(coins7, amount7);
    System.out.println("coins = " + coins7 + "，amount = " + amount7 + "，结果：" + result7);
  }

  /**
   * 按照给的币种面额，和总金额，计算出最少需要几张币可以加起来位总金额 如：[1,2,5]  ,amount=11,  计算是5+5+1 = 11; 返回是3 如：[2], ,amount=3,
   * 无法算出2=3; 返回是-1
   *
   * @param coins
   * @param amount
   * @return
   */
  public static int getMinCoinNum(int[] coins, int amount) {
    int len = coins.length;
    if (len == 1) {
      return coins[0] == amount ? 1 : -1;
    }
    //进行倒序排序
    for (int i = 0; i < coins.length - 1; i++) {
      for (int j = 0; j < coins.length - i - 1; j++) {
        if (coins[j] < coins[j + 1]) {
          int temp = coins[j];
          coins[j] = coins[j + 1];
          coins[j + 1] = temp;
        }
      }
    }

    //算法思路：一开始leftAmount = 总金额， leftAmount/cons[i] = 商...余数，余数不为0，继续，余数为leftAmount/[i],循环
    int leftAmount = amount;
    int count = 0;
    int minValue = coins[len - 1];
    for (int i = 0; i < len; i++) {
      if (coins[i] > leftAmount) {
        continue;
      }
      count += leftAmount / coins[i];
      int offset = leftAmount % coins[i];
      if (offset < minValue && offset
          > 0) { //小于最小值的话，补会一个当前被除掉的值，比如：29/7=4...1, count = 4 1 < 2;改成  1+ 7 , count -1 = 3
        offset += coins[i];
        count--;
      }
      leftAmount = offset;
      //判断这个值是否大于最小的一个数
      if (leftAmount == 0) {
        return count;
      }
    }
    if (leftAmount == 0) {
      return count;
    }

    return -1;
  }
}
